/**
 * 假设你正在爬楼梯，需要 n 阶你才能到达楼顶。
 * 每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * 注意：给定 n 是一个正整数。
 * <p>
 * 示例 1：
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 * <p>
 * 示例 2：
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/climbing-stairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author lixin
 */
public class Solution {

    // 1 1 -> 1+0=1
    // 2 1,1 / 2 -> 1+1=2
    // 3 1,1,1 / 1,2 / 2,1 -> 2+1=3
    // 4 1,1,1,1 / 1,1,2 / 1,2,1 / 2,1,1 / 2,2 -> 3+2=5
    // 5 1,1,1,1,1 / 1,1.1,2 / 1,2,1,1 / 1,1,2,1 / 1,2,2 / 2,1,1,1 / 2,1,2 / 2,2,1 -> 5+3=8
    // 6 ... -> 8+5=13
    // 7 ... -> 13+8=21
    // 8 ... -> 21+13=34
    // dp[n] = dp[n-1] + dp[n-2]
    public static long climbStairs(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 50; i++) {
            long startTime = System.nanoTime();
            System.out.print("n=" + i + "有");
            System.out.print(climbStairs(i));
            System.out.print("种方法，计算耗时：");
            System.out.print(System.nanoTime() - startTime);
            System.out.println("纳秒");
        }
    }

}
